1. Field of the Invention
The present invention relates to an apparatus and method for outputting a sequence of vectors, a data recording medium, and a carrier wave signal.
More particularly, the present invention relates to an apparatus and method for outputting a sequence of higher dimensional random vectors whose limiting distribution is expressed by an analytical density function, after associating two vector sequence generating methods by which sequences of random vectors whose limiting distribution is expressed by a known analytical density function are output, and a data recording medium storing a program which realize the above vector sequence output.
2. Description of the Related Art
Many random number generating methods utilizing recurrence formulas have been known conventionally. Many fields require random number generation. Monte-Carlo method for simulation in physics and engineering fields utilizes the random numbers.
CDMA (Code Division Multiple Access) technology for mobile phone communication assigns PN (Pseudo Noise) code to each user in order to share the limited band among many users. The PN code is generated based on the random numbers.
Moreover, public key encryption employed in telecommunication technologies utilizes the random numbers for generating public keys. Demands for such the encryption has been developing because stronger protection has been required as telecommunications such as internet has been widely used.
Traditional methods for generating the random numbers usually utilize recurrence formulas. Especially, multiplication recurrence formulas have been used widely for many years. However, such the multiplication recurrence formula also has raised problems regarding to finite periodicity. Recently, rational maps have been applied to the recurrence formulas to generate random numbers as chaos theory has been developing. The rational map is a result of the addition theorem of an elliptic function (including a trigonometric function). Demands for the random number generation by such the method which utilizes the rational map have been developing, because such the method has the following advantages.
(1) Non-cyclical random number sequence generation by which the numbers are proven to be chaotic (thus, aperiodic):
(2) Sequences of rational numbers result from rational number seeds (initial values given to the recurrence formula); and
(3) Known analytic function acts as the density function expressing random number distribution.
Known rational maps which bring the above advantages are: an Ulam-von Neumann map (equation 1), a cubic map (equation 2), a quintic map (equation 3), and the like.f(x)=4x(1−x)  EQUATION 1f(x)=x(3−4x)2  EQUATION 1f(x)=x(5−20x+16x2)2  EQUATION 3
Regardless of the different rational maps above, the equation 4 represents a density function expressing distribution of a random number sequence x[i] which results from the following recurrence formula (where 0<ξ<1; ξ is an arbitrary initial value).x[0]=ξx[i+1]=f(x[i])(i≧0)
                              ρ          ⁡                      (            x            )                          =                  1                      π            ⁢                                          x                ⁡                                  (                                      1                    -                    x                                    )                                                                                        EQUATION        ⁢                                  ⁢        4            
A rational map with a parameter, such as a Katsura-Fukuda map, a generalized Ulam-von Neumann map (equation 5), a generalized cubic map, a generalized Chebyshev map, or the like may be applied to the recurrence formula.
                                          f            ⁡                          (                              l                ,                m                ,                x                            )                                =                                                    4                ⁢                                  x                  ⁡                                      (                                          1                      -                      x                                        )                                                  ⁢                                  (                                      1                    -                    lx                                    )                                ⁢                                  (                                      1                    -                    mx                                    )                                                            1                -                                  Ax                  2                                +                                  Bx                  2                                +                                  Cx                  4                                                      ⁢                                                  ⁢            where                          ⁢                                  ⁢                  A          =                      2            ⁢                          (                              l                +                m                +                lm                            )                                      ⁢                                  ⁢                  B          =                      8            ⁢                          lm              2                                      ⁢                                  ⁢                  C          =                                    l              2                        +                          m              2                        -                          2              ⁢              lm                        -                          2              ⁢                              l                2                            ⁢              m                        -                          2              ⁢                              lm                2                                      +                                          l                2                            ⁢                              m                2                                                                        EQUATION        ⁢                                  ⁢        5            
For example, if the random number sequence result from the above recurrence formula employing the generalized Ulam-von Neumann map (equation 5), limiting distribution of the resultant random number sequences is expressed by the following density function (equation 6) which includes the parameter of the generalized Ulam-von Neumann map.
                                          1                                          K                ⁡                                  (                                      l                    ,                    m                                    )                                            ⁢                                                                    x                    ⁡                                          (                                              1                        -                        x                                            )                                                        ⁢                                      (                                          1                      -                      lx                                        )                                    ⁢                                      (                                          1                      -                      mx                                        )                                                                                ⁢                                          ⁢          where                ⁢                                  ⁢                              K            ⁡                          (                              l                ,                m                            )                                =                                    ∫              0              1                        ⁢                          du                                                                    (                                          1                      -                                              u                        2                                                              )                                    ⁢                                      (                                          1                      -                                              lu                        2                                                              )                                    ⁢                                      (                                          1                      -                                              mu                        2                                                              )                                                                                                          EQUATION        ⁢                                  ⁢        6            
The Katsura-Fukuda map is the same as the generalized Ulam-von Neumann map (equation 5) where m=0.
Unexamined Japanese Patent Application KOKAI No. H10-283344 by the inventor of the present invention discloses a technique for generating random numbers with utilizing rational maps. Theoretical backgrounds for the technique are disclosed in the following documents.    S. M. Ulam and J. von Neumann, Bull. Math. Soc. 53 (1947) pp. 1120.    R. L. Adler and T. J. Rivlin, Proc. Am. Math. Soc. 15 (1964) pp. 794.    K. Umeno, Method of constructing exactly solvable chaos, Phys. Rev.E (1997) Vol. 55 pp. 5280-5284.
Conventionally, a random number sequence (a sequence of random one-dimensional vectors) result from the above random number generating method by applying a sequence of scalars (one-dimensional vectors) to the recurrence formula as the seed.
However, such the conventional methods have the following problems.
For carrying out the Monte-Carlo method in dimension at least two, a sequence of random vectors of dimensions at least two is required. However, the conventional random number generating method generates a sequence of random numbers corresponding to a sequence of scalars (one-dimensional vectors). When the Monte-Carlo method is applied to simulation in three-dimensional space, three-value selection from head of the sequence may be required for necessary times. However, such operation causes deviation of random number distribution, thus, error convergence will be poor.
Moreover, the public key encryption requires paired integers as the random number. However, the conventional method can not perform simultaneous generation of the integers to be paired. This will make a security hole, thus, the encryption may be cracked.
Under such the circumstances, there is a great demand for an apparatus and method for outputting a sequence of vectors each of which comprises plural pairs of random numbers each being generated simultaneously as a multi-dimensional random vector, and for expressing distribution of the output vector sequence by an analytic density function.